#include <algorithm>
#include <vector>

class Solution
{
 public:
  int nthUglyNumber(int n)
  {
    // p2，p3，p5分别为三个队列的指针，newNum为从队列头选出来的最小数
    int p2 = 0, p3 = 0, p5 = 0, newNum = 1;
    std::vector<int> arr;
    arr.push_back(newNum);
    while (arr.size() < index)
    {
      // 选出三个队列头最小的数
      newNum = std::min(arr[p2] * 2, std::min(arr[p3] * 3, arr[p5] * 5));
      // 这三个if有可能进入一个或者多个，进入多个是三个队列头最小的数有多个的情况
      if (arr[p2] * 2 == newNum) p2++;
      if (arr[p3] * 2 == newNum) p3++;
      if (arr[p5] * 2 == newNum) p5++;
      arr.push_back(newNum);
    }
    return newNum;
  }
};